package 动态规划;

public class LeetCode45_跳跃游戏2 {
    // 每一次的操作，都执行当前这一步的最优解，走到最后，
    public int jump(int[] nums) {
        int index = 0, nextIndex = 0;
        int jumpCount = 0, max = 0;
        while(index<nums.length-1){  // 倒数第二位，只要到倒数第二位就可以跳导终点
            int step = nums[index];
            // 从index的下一步开始走
            for(int i=index+1; i<nums.length&&i<=index+step; i++){
                if(i == nums.length - 1){
                    jumpCount++; // 直接碰到了数组右边界
                    return jumpCount;
                }
                // 从i 出发能到达最远的地方
                int current = i+nums[i];
                if(current>max){
                    max = current;
                    nextIndex = i;  // 如果大于最远的地方，更新nextIndex
                }
            }
            index = nextIndex;  // 找到了下一个index
            jumpCount++;
        }
        return jumpCount;
    }
}
